Всего у нас три ко­ор­ди­на­ты, по каж­дой есть ми­ни­мум и мак­си­мум, ко­то­рые раз­лич­ны, так как про­ек­ции не лежат на одной пря­мой. Тогда по прин­ци­пу Ди­ри­х­ле для не­ко­то­рой из точек какие-то две ко­ор­ди­на­ты при­ни­ма­ют зна­че­ния ми­ни­му­ма или мак­си­му­ма. Тогда про­ек­ция этой точки на любую ко­ор­ди­нат­ную плос­кость имеет как ми­ни­мум одну из ко­ор­ди­нат ми­ни­маль­ной или мак­си­маль­ной, от­ку­да точка не может быть внут­ри вы­пук­лой обо­лоч­ки дру­гих точек.

Ответ: нет, не могло.

По прин­ци­пу Ди­ри­х­ле как ми­ни­мум в одном фи­ли­а­ле как ми­ни­мум 41 участ­ник и как ми­ни­мум 21 из них од­но­го пола. Тре­бу­ет­ся до­ка­зать, что по мень­шей мере 5 из этих 21 участ­ни­ка од­но­го воз­рас­та. Если это не так, то су­ще­ству­ет не более 4 участ­ни­ков из каж­дой воз­раст­ной груп­пы. В груп­пе из 21 че­ло­ве­ка как ми­ни­мум 6 воз­раст­ных групп, и если мы возь­мем по пред­ста­ви­те­лю из каж­дой воз­раст­ной груп­пы, то оче­вид­но по­лу­чим про­ти­во­ре­чие с одним из усло­вий за­да­чи.

Сумма двух чётных на­ту­раль­ных чисел все­гда чётна и боль­ше двух, сле­до­ва­тель­но, не может быть про­стым чис­лом. По­это­му при­мер мно­же­ства из всех пя­ти­де­ся­ти чётных чисел, не пре­вос­хо­дя­щих 100 по­ка­зы­ва­ет, что ми­ни­маль­ное n не мень­ше 51. С дру­гой сто­ро­ны, разобьём все на­ту­раль­ные числа от 1 до 100 на 50 пар, сумма чисел в каж­дой из ко­то­рых равна про­сто­му числу 101: 1 и 100, 2 и 99, …, 50 и 51. Если в вы­бран­ном мно­же­стве не мень­ше 51 числа, то, по прин­ци­пу Ди­ри­х­ле, хотя бы два из них по­па­дут в одну пару, и их сумма будет про­стым чис­лом.

Ответ:

а)  Один из пря­мо­уголь­ни­ков раз­би­е­ния дол­жен иметь пло­щадь не мень­ше, чем обо­зна­чим его сто­ро­ны за x и y. По не­ра­вен­ству о сред­нем ариф­ме­ти­че­ском и сред­ним гео­мет­ри­че­ском имеем зна­чит, пе­ри­метр этого пря­мо­уголь­ни­ка, рав­ный не мень­ше Это зна­че­ние до­сти­га­ет­ся для раз­би­е­ния квад­ра­та на 25 оди­на­ко­вых квад­ра­ти­ков со сто­ро­ной 0,2.

С дру­гой сто­ро­ны, раз­би­е­ние квад­ра­та на 25 рав­ных пря­мо­уголь­ни­ков со сто­ро­на­ми 1 и даёт при­мер по­это­му p мак­си­маль­ное точно боль­ше 2. В любом раз­би­е­нии еди­нич­но­го квад­ра­та на 25 пря­мо­уголь­ни­ков найдётся пря­мо­уголь­ник пло­ща­ди не боль­ше обо­зна­чим его сто­ро­ны за и при этом и Сле­до­ва­тель­но, дол­жен най­тись такой x из ин­тер­ва­ла для ко­то­ро­го Дан­ная функ­ция яв­ля­ет­ся квад­ра­тич­ной с от­ри­ца­тель­ным стар­шим ко­эф­фи­ци­ен­том, по­это­му её ми­ни­мум на от­рез­ке при­ни­ма­ет­ся в одном из кон­цов этого от­рез­ка. Со­от­вет­ству­ю­щие зна­че­ния на кон­цах равны Сле­до­ва­тель­но, и

Ответ: а) Ми­ни­маль­ное зна­че­ние p равно мак­си­маль­ное зна­че­ние p равно б) Да, можно, спо­соб ука­зан в ре­ше­нии.

По­ка­жем, как Пете сде­лать так, чтобы на одной из та­ре­ло­чек ско­пи­лось не менее 32 пи­рож­ных. За­ну­ме­ру­ем та­ре­лоч­ки по кругу но­ме­ра­ми от 0 до 2018. По­кра­сим в крас­ный цвет 32 та­ре­лоч­ки та­ре­лоч­ки с но­ме­ра­ми Петя будет ука­зы­вать лишь на та­ре­лоч­ки с но­ме­ра­ми от 0 до а про осталь­ные за­бу­дет. Вна­ча­ле он ука­жет на все пи­рож­ки, ле­жа­щие на та­ре­лоч­ках с не­чет­ны­ми но­ме­ра­ми (из этого про­ме­жут­ка) и по­тре­бу­ет сдви­нуть их на одну по­зи­цию. В ре­зуль­та­те не­чет­ные та­ре­лоч­ки опу­сте­ют, а все пи­рож­ки с них ско­пят­ся на чет­ных та­ре­лоч­ках (и при этом не вый­дут за пре­де­лы этого про­ме­жут­ка). Затем он ука­жет на все пи­рож­ки на та­ре­лоч­ках вида и по­тре­бу­ет сдви­нуть их на 2. В ре­зуль­та­те все эти пи­рож­ки ско­пят­ся на та­ре­лоч­ках (из на­ше­го про­ме­жут­ка) с но­ме­ра­ми, крат­ны­ми че­ты­рем. Далее он вы­даст ана­ло­гич­ные ука­за­ния для та­ре­ло­чек вида (сдви­нуть на 4) и, вида (сдви­нуть на 8), на­ко­нец, вида (сдви­нуть на 16). В ре­зуль­та­те этой де­я­тель­но­сти все пи­рож­ков ока­жут­ся на 32 крас­ных та­ре­лоч­ках. По прин­ци­пу Ди­ри­х­ле, на одной из них ока­жет­ся не менее 32 пи­рож­ков.

Те­перь на­учим Васю, как не до­пу­стить более 32 пи­рож­ков ни на одну та­ре­лоч­ку. Пусть Вася со­по­ста­вит каж­дой та­ре­лоч­ке блок из 32 та­ре­ло­чек, со­дер­жа­щий эту та­ре­лоч­ку и 31 сле­ду­ю­щие за ней по ча­со­вой стрел­ке. Вася будет сле­дить за тем, чтобы ис­ход­ный пи­ро­жок с каж­дой та­ре­лоч­ки пе­ре­ме­щал­ся лишь в пре­де­лах со­по­став­лен­но­го ей блока. (Оче­вид­но, что это воз­мож­но: на каком бы месте этого блока дли­ной 32 та­ре­лоч­ки не лежал пи­ро­жок, и какое бы сдвиг от 1 до 16 не на­звал Петя, Вася смо­жет вы­брать на­прав­ле­ние так, чтобы пи­ро­жок не вышла пре­де­лы этого блока.) Но каж­дая та­ре­лоч­ка со­дер­жит­ся ровно в 32 таких бло­ках, и на ней могут ока­зать­ся лишь пи­рож­ки, пе­ре­ме­ща­ю­щи­е­ся по этим бло­кам, то есть не более 32 пи­рож­ков!

Ответ: 32.

Сна­ча­ла по­ка­жем, что рас­сто­я­ние до бли­жай­ше­го це­ло­го числа от числа вида (где q  — ир­ра­ци­о­наль­ное и c  — любое фик­си­ро­ван­ное число) можно вы­бо­ром m сде­лать сколь угод­но малым. Рас­смот­рим чисел q, 2q, 3q, ..., Их дроб­ные части по­па­да­ют в один из n про­ме­жут­ков

Тогда по прин­ци­пу Ди­ри­х­ле най­дут­ся два числа m₁q и m2_q дроб­ные доли ко­то­рых по­па­ли в один и тот же про­ме­жу­ток. Их раз­ность

также яв­ля­ет­ся чис­лом вида mq, причём, по­сколь­ку раз­ность их дроб­ных ча­стей по мо­ду­лю мень­ше для не­ко­то­ро­го це­ло­го N верно не­ра­вен­ство

Сле­до­ва­тель­но, су­ще­ству­ет такое число что Вы­бе­рем на­ту­раль­ное число l так, что вы­пол­ня­ет­ся одно из двой­ных не­ра­венств или Тогда найдётся такое целое число K, что

то есть

Сле­до­ва­тель­но,

где Зна­чит, рас­сто­я­ние от це­ло­го числа −K до числа мень­ше Уве­ли­чи­вая зна­че­ние n, можно сде­лать это рас­сто­я­ние сколь угод­но малым.

Без огра­ни­че­ния общ­но­сти будем счи­тать, что При пре­об­ра­зо­ва­нии по­до­бия пря­мой с ко­эф­фи­ци­ен­том точка −a пе­рейдёт в точку −1, а точка b  — в точку Куз­не­чик те­перь будет пры­гать на 1 впра­во и на влево. В не­ко­то­рый мо­мент куз­не­чик пе­ре­сечёт се­ре­ди­ну от­рез­ка прыж­ком на 1 впра­во и попадёт в не­ко­то­рую точку c. После этого куз­не­чик ни­ко­гда не будет де­лать прыж­ки длины q более од­но­го раза под­ряд. При прыж­ке на 1 дроб­ные доли точек, в ко­то­рых куз­не­чик на­хо­дил­ся до и после прыж­ка, оди­на­ко­вые.

Пусть куз­не­чик на­хо­дит­ся в точке c. Вы­бе­рем такое на­ту­раль­ное число m, что рас­сто­я­ние от c – mq до бли­жай­ше­го це­ло­го мень­ше Если куз­не­чик сде­ла­ет m прыж­ков влево, он будет на­хо­дить­ся на рас­сто­я­нии менее от ка­ко­го-то це­ло­го числа, не­за­ви­си­мо от того, сколь­ко при этом он со­вер­шил прыж­ков впра­во на 1. По­сколь­ку точка 0 на­хо­дит­ся левее се­ре­ди­ны на­ше­го от­рез­ка, то, пры­гая на 1 впра­во, куз­не­чик обя­за­тель­но ока­жет­ся на рас­сто­я­нии менее от точки 0, а на ис­ход­ной пря­мой  — на рас­сто­я­нии, мень­шем 10⁻⁶ от точки 0.

При­ве­дем дру­гое ре­ше­ние.

Не­за­ви­си­мо от сво­е­го на­чаль­но­го по­ло­же­ния x₀ куз­не­чик рано или позд­но ока­жет­ся на про­ме­жут­ке

Дей­стви­тель­но, если то он будет пры­гать впра­во на a, пока не пе­ре­прыг­нет точку и не ока­жет­ся на про­ме­жут­ке

а если то он будет пры­гать влево на b, пока не пе­ре­прыг­нет точку и не ока­жет­ся на про­ме­жут­ке

При даль­ней­ших прыж­ках куз­не­чик уже не по­ки­нет про­ме­жут­ка Δ: ока­зав­шись на Δ_r он пры­га­ет влево на b и по­па­да­ет на Δ_l, а ока­зав­шись на Δ_l, он пры­га­ет впра­во на a и по­па­да­ет на Δ_r.

Если скле­ить про­ме­жу­ток Δ в окруж­ность той же длины то ука­зан­ные прыж­ки куз­не­чи­ка на этой окруж­но­сти будут уже прыж­ка­ми в одну сто­ро­ну на a (или в дру­гую сто­ро­ну на b, что на дан­ной окруж­но­сти  — одно и то же). По­сколь­ку от­но­ше­ние прыж­ка a к длине a + b окруж­но­сти ир­ра­ци­о­наль­но, следы куз­не­чи­ка будут всюду плот­ны на окруж­но­сти, то есть рано или позд­но куз­не­чик попадёт на вся­кую дугу окруж­но­сти. Сле­до­ва­тель­но, и на ис­ход­ном про­ме­жут­ке Δ следы куз­не­чи­ка всюду плот­ны, так что рано или позд­но он попадёт в любую на­пе­ред за­дан­ную окрест­ность нуля.

Для про­из­воль­но­го фик­си­ро­ван­но­го на­ту­раль­но­го m рас­смот­рим мно­же­ство из числа a₁, a₂, ..., a_m + 1, все они по усло­вию, раз­лич­ны и не пре­вос­хо­дят 2m. Разобьём все на­ту­раль­ные числа от 1 до 2m на m пар

по прин­ци­пу Ди­ри­х­ле одна из этих пар со­дер­жит два из чисел a₁, a₂, ..., a_m + 1, ко­то­рые и об­ра­зу­ют ис­ко­мую в усло­вии пару чле­нов по­сле­до­ва­тель­но­сти с раз­ни­цей m. Что тре­бо­ва­лось до­ка­зать.

Раз­де­лим квад­рат на 25 квад­ра­тов со сто­ро­ной Если бы в каж­дом из них было не более двух точек, то всего точек ока­за­лось бы не более пя­ти­де­ся­ти (прин­цип Ди­ри­х­ле). Ответ на во­прос о круге будет по­ло­жи­те­лен. (За­ме­тим, что без сфор­му­ли­ро­ван­но­го утвер­жде­ния о квад­ра­ти­ке было бы зна­чи­тель­но труд­нее до­га­дать­ся до идеи ре­ше­ния.) В самом деле, нам оста­лось убе­дить­ся, что в круге ра­ди­у­са со­дер­жит­ся квад­рат со сто­ро­ной по­сколь­ку ра­ди­ус опи­сан­ной окруж­но­сти для квад­ра­та равен и

Рас­смот­рим ко­ман­ду А, одер­жав­шую в тур­ни­ре мак­си­маль­ное число побед, обо­зна­чим это число через k. Ко­ман­ды, про­иг­рав­шие А, сыг­ра­ли между собой игр, в ко­то­рых в сумме одер­жа­ли такое же ко­ли­че­ство побед, сле­до­ва­тель­но, по усло­вию долж­но вы­пол­нять­ся не­ра­вен­ство: от­ку­да Рас­смот­рим все три слу­чая.

1)  Когда При этом не­ра­вен­ство ста­но­вит­ся точ­ным, сле­до­ва­тель­но, ко­ман­ды, про­иг­рав­шие А, долж­ны про­иг­рать и всем ко­ман­дам, вы­иг­рав­шим у А. Если есть хотя бы одна такая ко­ман­да, то она одер­жа­ла не менее побед, что боль­ше, чем у А  — про­ти­во­ре­чие с вы­бо­ром А. Зна­чит, ко­ли­че­ство ко­манд в этом слу­чае не боль­ше 4, то есть в точ­но­сти равно 4. При­мер та­ко­го тур­ни­ра: А вы­иг­ра­ла у Б, В и Г, Б вы­иг­ра­ла у В, В вы­иг­ра­ла у Г, Г вы­иг­ра­ла у Б.

2)  Когда Пусть А вы­иг­ра­ла у Б и В, при этом можно счи­тать, что Б вы­иг­ра­ла у В. Если есть хотя бы две ко­ман­ды Г и Д, вы­иг­рав­шие у А, при этом Г вы­иг­ра­ла у Д, то у Г уже две по­бе­ды над А и Д и не может быть дру­гих, зна­чит, она про­иг­ра­ла ко­ман­дам Б и В. В таком слу­чае, ко­ман­ды Б и В в сумме одер­жа­ли не менее трёх побед  — Б и В на Г и Б на В а а это боль­ше числа побед у А, что про­ти­во­ре­чит усло­вию. Таким об­ра­зом, в дан­ном слу­чае может быть не более одной ко­ман­ды, вы­иг­рав­шей у А, и общее число ко­манд не может пре­вос­хо­дить 4. При­мер тур­ни­ра с 4 ко­ман­да­ми: А вы­иг­ра­ла у Б, Б вы­иг­ра­ла у В, В вы­иг­ра­ла у А, Г про­иг­ра­ла А, Б и В. Трёх ко­манд здесь быть не может, так как про­иг­рав­шие А ко­ман­ды Б и В в сумме могут одер­жать толь­ко одну по­бе­ду (между собой).

3)  Когда Число ко­манд в дан­ном слу­чае не пре­вос­хо­дит 3, так, как общее число побед в тур­ни­ре n ко­манд равно и, по прин­ци­пу Ди­ри­х­ле, одна из них одер­жа­ла не менее

побед, от­ку­да При­мер тур­ни­ра трёх ко­манд в дан­ном слу­чае оче­ви­ден: А вы­иг­ра­ла у Б, Б вы­иг­ра­ла у В, В вы­иг­ра­ла у А. Слу­чай двух ко­манд не­воз­мо­жен, так как ко­ман­да, про­иг­рав­шая А не смо­жет одер­жать ни одной по­бе­ды.

Ответ: три или че­ты­ре.

Без огра­ни­че­ния общ­но­сти пусть кле­ток чёрного цвета не мень­ше 32, тогда можно оста­вить толь­ко 32 из них и мак­си­мум, есте­ствен­но, не уве­ли­чит­ся. Со­от­вет­ствен­но, будем ре­шать за­да­чу для ровно 32 чёрных кле­ток.

Пусть мы можем вы­брать две строч­ки, в ко­то­рых сум­мар­но n чёрных кле­ток. Тогда в осталь­ных 6 стро­ках чёрных кле­ток, ко­то­рые на­хо­дят­ся в 8 столб­цах из 6 кле­ток. По прин­ци­пу Ди­ри­х­ле среди них можно вы­брать два столб­ца, в ко­то­рых не мень­ше чёрных кле­ток. По­лу­чит­ся не мень­ше

что стро­го боль­ше 15, если n хотя бы 10. Сле­до­ва­тель­но, если можно вы­брать две стро­ки/столб­ца, в ко­то­рых сум­мар­но не менее 10 чёрных кле­ток, то можно вы­брать крест с не менее, чем 16 чёрными клет­ка­ми.

Те­перь пред­по­ло­жим, что в любых двух строч­ках и любых двух столб­цах не более 9 чёрных кле­ток. Тогда:

1)  Не может быть стро­ки или столб­ца с 6 и более клет­ка­ми чёрного цвета, так как тогда по прин­ци­пу Ди­ри­х­ле найдётся стро­ка с 4 и более клет­ка­ми чёрного цвета.

2)  Не может быть двух строк или двух столб­цов с 5 чёрными клет­ка­ми. Сле­до­ва­тель­но, набор ко­ли­че­ства чёрных кле­ток в стро­ках/столб­цах может быть либо 54444443, либо 44444444 чёрных кле­ток, то есть су­ще­ству­ет не менее 6 строк, в ко­то­рых ровно 4 чёрных и 4 белых.

Пусть во всех столб­цах по 4 чёрных клет­ки. Рас­смот­рим три любые стро­ки из 6, в ко­то­рых по 4 белых клет­ки. Най­дут­ся две стро­ки, в двух столб­цах ко­то­рых толь­ко белые клет­ки (так как в про­тив­ном слу­чае белые клет­ки есть ми­ни­мум в 4+3+2 = 9 столб­цах). Так как в этих столб­цах по 4 чер­ных клет­ки, то сум­мар­но в вы­бран­ных строч­ках и этих столб­цах най­дут­ся 16 чер­ных кле­ток. Ана­ло­гич­но по­сту­пим, если во всех стро­ках по 4 чер­ные клет­ки.

Если же и в стро­ках, и в столб­цах ко­ли­че­ства чёрных кле­ток равны 54444443, то вы­бе­рем строч­ку и стол­бец, в ко­то­рых по 5 чёрных кле­ток, то есть сум­мар­но не менее 9. Среди 7 осталь­ных столб­цов есть не менее двух, ко­то­рые пе­ре­се­ка­ют­ся с вы­бран­ной стро­кой по белой клет­ке, и среди этих двух есть не менее од­но­го столб­ца, в ко­то­ром ровно 4 чёрных клет­ки. Точно так же среди осталь­ных 7 строк най­дет­ся хотя бы одна такая, в ко­то­рой ровно 4 чёрных клет­ки, а с пер­вым вы­бран­ным столб­цом она пе­ре­се­ка­ет­ся по белой. Вы­бран­ная стро­ка может пе­ре­сечь­ся по чёрной клет­ке со вто­рым вы­бран­ным столб­цом, по­это­му она до­ба­вит не более чем 3 чёрные клет­ки. До­ба­вим эти стро­ку и стол­бец к вы­бран­ным. Итого в них не менее чер­ных кле­ток. В итоге мы до­ка­за­ли, что Вася может га­ран­ти­ро­ван­но вы­брать 16 кле­ток од­но­го цвета.

При­ме­ром того, что вы­брать боль­ше 16 кле­ток у Васи не все­гда по­лу­чит­ся, яв­ля­ет­ся шах­мат­ная рас­крас­ка. В каж­дой стро­ке и в каж­дом столб­це ровно по 4 белых и 4 чёрных клет­ки, зна­чит, в любых 2 столб­цах и 2 стро­ках сум­мар­но будет вы­бра­но не более, чем од­но­цвет­ных кле­ток.

Ответ: 16.

Каж­дое из про­из­ве­де­ний чисел, сто­я­щих в де­ся­ти стро­ках таб­ли­цы, пред­ста­вим в виде про­из­ве­де­ния про­стых со­мно­жи­те­лей. Вы­пи­шем по­след­ние один­на­дцать про­стых не пре­вы­ша­ю­щие 200: 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199. За­ме­тим, что каж­дое из этих один­на­дца­ти чисел может встре­тить­ся толь­ко в одном из этих де­ся­ти про­из­ве­де­ний, по­сколь­ку числа, крат­ные лю­бо­му из них боль­ше 200. Сле­до­ва­тель­но, най­дет­ся стро­ка x, про­из­ве­де­ние чисел в ко­то­рой будет со­дер­жать не менее двух из ука­зан­ных мно­жи­те­лей (по прин­ци­пу Ди­ри­х­ле). Эти мно­жи­те­ли будут рас­по­ла­гать­ся в раз­ных столб­цах. Два таких мно­жи­те­ля обо­зна­чим через m и n. Рас­смот­рим те­перь про­из­ве­де­ния чисел, сто­я­щих в столб­цах таб­ли­цы. Так как числа m и n не могут рас­по­ла­гать­ся в одном столб­це, то ни одно из про­из­ве­де­ний в столб­цах не может сов­пасть с про­из­ве­де­ни­ем чисел, сто­я­щих в стро­ке x. Сле­до­ва­тель­но, по­лу­чен­ные на­бо­ры не могут ока­зать­ся оди­на­ко­вы­ми.

Ответ: нет, не могли.

Каж­дое из про­из­ве­де­ний чисел, сто­я­щих в де­ся­ти стро­ках таб­ли­цы, пред­ста­вим в виде про­из­ве­де­ния про­стых со­мно­жи­те­лей. Вы­пи­шем по­след­ние один­на­дцать про­стых не пре­вы­ша­ю­щие 201: 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199. За­ме­тим, что каж­дое из этих один­на­дца­ти чисел может встре­тить­ся толь­ко в одном из этих де­ся­ти про­из­ве­де­ний, по­сколь­ку числа, крат­ные лю­бо­му из них боль­ше 201. Сле­до­ва­тель­но, най­дет­ся стро­ка x, про­из­ве­де­ние чисел в ко­то­рой будет со­дер­жать не менее двух из ука­зан­ных мно­жи­те­лей (по прин­ци­пу Ди­ри­х­ле). Эти мно­жи­те­ли будут рас­по­ла­гать­ся в раз­ных столб­цах. Два таких мно­жи­те­ля обо­зна­чим через m и n. Рас­смот­рим те­перь про­из­ве­де­ния чисел, сто­я­щих в столб­цах таб­ли­цы. Так как числа m и n не могут рас­по­ла­гать­ся в одном столб­це, то ни одно из про­из­ве­де­ний в столб­цах не может сов­пасть с про­из­ве­де­ни­ем чисел, сто­я­щих в стро­ке x. Сле­до­ва­тель­но, по­лу­чен­ные на­бо­ры не могут ока­зать­ся оди­на­ко­вы­ми.

Ответ: нет, не могли.

Лемма. Среди любых пяти узлов сетки из пра­виль­ных тре­уголь­ни­ков най­дут­ся два, се­ре­ди­на от­рез­ка между ко­то­ры­ми  — тоже узел сетки.

До­ка­за­тель­ство. Введём на­ча­ло отсчёта в одном из узлов сетки и обо­зна­чим за и ра­ди­ус-век­то­ры к двум бли­жай­шим узлам, как на верх­нем ри­сун­ке. Тогда узлы сетки суть точки вида для целых m и n. По прин­ци­пу Ди­ри­х­ле из пяти точек най­дут­ся две точки и у ко­то­рых од­но­вре­мен­но сов­па­да­ет чётность m₁ и m₂ и чётность n₁ и n₂. Се­ре­ди­на от­рез­ка, со­еди­ня­ю­ще­го эти две точки, есть точка

Она яв­ля­ет­ся узлом сетки, так как числа и яв­ля­ют­ся це­лы­ми в силу оди­на­ко­вой чётно­сти m₁ и m₂, n₁ и n₂.

На ри­сун­ке слева можно уви­деть при­мер рас­по­ло­же­ния 8 узлов сетки, среди ко­то­рых нет двух, се­ре­ди­на от­рез­ка между ко­то­ры­ми  — узел сетки. До­ка­жем, что де­вя­ти узлов до­ста­точ­но. За­ме­тим, что ше­сти­уголь­ная сетка раз­би­ва­ет­ся в объ­еди­не­ние двух тре­уголь­ных (см. ниж­ний ри­су­нок). По прин­ци­пу Ди­ри­х­ле среди любых де­вя­ти узлов по край­ней мере пять ока­жут­ся в одной из этих двух тре­уголь­ных сеток. По лемме среди этих пяти узлов най­дут­ся два ис­ко­мых.

Ответ: 9.

Ком­мен­та­рий.

Тре­уголь­ная сетка из леммы ле­ле­ет­ся сет­кой из рав­ных па­рал­ле­ло­грам­мов, если сте­реть я лиш­ние линии. А утвер­жде­ние про квад­рат­ную сетку из усло­вия за­да­чи также спра­вед­ли­во для любой сетки из рав­ных па­рал­ле­ло­грам­мов. Таким об­ра­зом, в усло­вии за­да­чи при­сут­ство­ва­ла в каком-то смыс­ле под­сказ­ка.

Пусть в ко­роб­ке лежат n нос­ков, тогда, по прин­ци­пу Ди­ри­х­ле, нос­ков ка­ко­го-то цвета не боль­ше сле­до­ва­тель­но, осталь­ных  — не мень­ше причём их долж­но быть мень­ше 25 (по усло­вию). По­лу­ча­ем

Число 29 не под­хо­дит, по­то­му что тогда в ко­роб­ке будут носки од­но­го цвета в ко­ли­че­стве не более 4 штук, а нос­ков осталь­ных цве­тов  — не менее 25, что про­ти­во­ре­чит усло­вию. Для сле­ду­ю­ще­го числа 28 су­ще­ству­ет си­ту­а­ция (для каж­до­го из 7 цве­тов  — 4 носка), удо­вле­тво­ря­ю­щая усло­вию за­да­чи.

Ответ: 28.

Рас­смот­рим об­щи­тель­ное мно­же­ство A наи­мень­ше­го раз­ме­ра. За­ме­тим, что можно вы­брать A таким, что для каж­до­го тро­гло­ди­та a из A най­дет­ся тро­гло­дит v_a един­ствен­ный друг ко­то­ро­го в мно­же­стве A  — тро­гло­дит a. Дей­стви­тель­но, в про­тив­ном слу­чае, если a дру­жит с кем-то из A, то его можно про­сто уда­лить, а если не дру­жит ни с кем из A, то её можно по­ме­нять с любым его дру­гом.

По прин­ци­пу Ди­ри­х­ле не­ко­то­рый тро­гло­дит зна­ком с хотя бы тро­гло­ди­та­ми не из A.

Пусть B  — мно­же­ство мак­си­маль­но­го раз­ме­ра, со­дер­жа­щее u и такое, что в нем никто не дру­жит. За­ме­тим, что B яв­ля­ет­ся стран­ным об­щи­тель­ным, оце­ним его раз­мер. За­ме­тим, что B не со­дер­жит дру­зей u, а также не более од­но­го тро­гло­ди­та из каж­дой пары a, v_a, где

По­сколь­ку дру­зья u, не вхо­дя­щие в A, по по­стро­е­нию не вхо­дят в пары и их не менее по­лу­ча­ем

Обо­зна­чим где a, b, c  — цифры его сотен, де­сят­ков и еди­ниц со­от­вет­ствен­но. Из прин­ци­па Ди­ри­х­ле и усло­вия сле­ду­ет, что все они раз­лич­ны, так как нель­зя рас­са­дить ми­ни­мум 4 кро­ли­ков (две пары оди­на­ко­вых цифр в А и В) по 3 клет­кам (раз­ря­дам), чтобы каж­до­му до­ста­лось от­дель­ное жильё. По усло­вию либо либо Кроме того, раз­ность А и В дву­знач­на, сле­до­ва­тель­но, пер­вая цифра А боль­ше пер­вой цифры В на 1 (как мы за­ме­ти­ли, пер­вые цифры этих чисел не могут быть равны). Рас­смот­рим оба слу­чая.

1.  Если Тогда   — дву­знач­ное число, де­ля­ще­е­ся на 9 и яв­ля­ю­ще­е­ся точ­ным квад­ра­том, то есть 36 или 81. В пер­вом слу­чае и то от­ку­да b  =  1, 2 и A  =  218, 329  — два ре­ше­ния. Во вто­ром слу­чае и a  =  b + 1, зна­чит, b + 2  =  c, от­ку­да b  =  1, 2, ..., 7 и A  =  213, ..., 879  — семь ре­ше­ний.

2.  Если Тогда   — дву­знач­ное число, де­ля­ще­е­ся на 9 и яв­ля­ю­ще­е­ся точ­ным квад­ра­том, то есть 36 или 81. В пер­вом слу­чае и a  =  c + 1, тогда c  =  b + 6 и a  =  b + 7, от­ку­да b  =  0, 1, 2 и A  =  706, 817, 928  — три ре­ше­ния. Во вто­ром слу­чае и a  =  c + 1, зна­чит, c  =  b + 1, a  =  b + 2, от­ку­да b  =  0, 1, 2, ..., 7 и A  =  201, 312, ..., 978  — во­семь ре­ше­ний. Общее число ре­ше­ний равно 2 + 7 + 3 + 8  =  20.

Ответ: всего 20 ре­ше­ний: A  =  218, 329, A  =  213, ..., 879, A  =  706, 817, 928, A  =  201, 312, ..., 978.

Возь­мем всех школь­ни­ков из какой-либо ко­ман­ды с пер­во­го урока и по­смот­рим, как они рас­пре­де­лят­ся по трем ко­ман­дам на вто­ром уроке. Так как рас­пре­де­ля­ют­ся 10 че­ло­век по трем ко­ман­дам, то по прин­ци­пу Ди­ри­х­ле най­дет­ся ко­ман­да, в ко­то­рую по­па­дут как ми­ни­мум 4 че­ло­ве­ка.

Те­перь возь­мем этих чет­ве­рых и по­смот­рим на их рас­пре­де­ле­ние по ко­ман­дам на тре­тьем уроке. По­сколь­ку ко­манд по-преж­не­му три, то по прин­ци­пу Ди­ри­х­ле най­дет­ся такая ко­ман­ду, в ко­то­рой будет как ми­ни­мум двое че­ло­век из рас­смат­ри­ва­е­мых че­ты­рех. Легко за­ме­тить, что эти двое были в одной ко­ман­де и на пер­вом уроке, и на вто­ром, и ока­за­лись в одной ко­ман­де на тре­тьем.

При­ведём дру­гое ре­ше­ние.

На каж­дом уроке физ­куль­ту­ры каж­дый школь­ник по­па­да­ет в одну из трех ко­манд; будем обо­зна­чать ко­ман­ды циф­ра­ми 1, 2 и 3. По­это­му уча­стие в ко­ман­дах на трех уро­ках под­ряд для каж­до­го школь­ни­ка можно опи­сать трой­кой чисел x-y-z, где каж­дое из x, y и z при­ни­ма­ет­ся зна­че­ний 1, 2 или 3. Таких раз­лич­ных троек су­ще­ству­ет Но школь­ни­ков по усло­вию за­да­чи 30, сле­до­ва­тель­но, по прин­ци­пу Ди­ри­х­ле най­дут­ся два школь­ни­ка, уча­стие ко­то­рых в ко­ман­дах опи­сы­ва­ет­ся оди­на­ко­вы­ми трой­ка­ми. Это те школь­ни­ки, ко­то­рые были в одной ко­ман­де в те­че­ние трех уро­ков под­ряд.